package com.learn.acm.bytedance;

/**
 *
 *
 *
 * @author zhongshitao
 * @date 2020/9/23 4:29 下午
 */
public class Solution215 {



    public int findKthLargest(int[] nums, int k) {
        return qSort(nums,0,nums.length-1,nums.length-k);
    }

    public int qSort(int[] nums, int low, int high, int index) {
        if (low < high) {
            int pivotKey = partation(nums,low,high);
            if (pivotKey == index) {
                return nums[index];
            } else if (pivotKey < index) {
                qSort(nums, pivotKey + 1, high, index);
            } else {
                qSort(nums, low, pivotKey-1, index);
            }
        }
        return 0;
    }

    private int partation(int[] nums, int low, int high) {
        int pivot = low;
        int index = pivot + 1;
        for (int i = index; i<= high; i++) {
            if (nums[i] < nums[pivot]) {
                swap(nums,i,index);
                index++;
            }
        }
        swap(nums,pivot, index-1);
        return index-1;
    }

    private void swap(int[] nums, int l, int h) {
        int t = nums[l];
        nums[l] = nums[h];
        nums[h] = t;
    }

}
